#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>

#define MIN(x, y) ((x) < (y) ? (x) : (y))

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

typedef struct TreeNode *Type;
typedef struct {
    Type *data;
    int size;
    int capacity;
} Queue;

void init(Queue *q)
{
    q->size = 0;
    q->capacity = 256;
    q->data = (Type *) malloc(q->capacity * sizeof(Type));
}

void destroy(Queue *q)
{
    q->size = 0;
    free(q->data);
}

void push(Queue *q, Type data)
{
    if (q->size == q->capacity) {
        Type *tmp = (Type *) malloc(2 * q->capacity * sizeof(Type));
        memcpy(tmp, q->data, q->capacity * sizeof(Type));
        free(q->data);
        q->data = tmp;
        q->capacity *= 2;
    }
    q->data[q->size++] = data;
}

Type pop(Queue *q)
{
    if (q->size == 0) {
        return 0;
    }
    Type result = q->data[0];
    memmove(q->data, q->data + 1, (q->size - 1) * sizeof(Type));
    q->size--;
    return result;
}

#define MAX_DEEP 2000

int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes)
{
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    int **result = (int **) malloc(MAX_DEEP * sizeof(int *));
    int *resultColSize = (int *) malloc(MAX_DEEP * sizeof(int));
    int resultSize = 0;

    Queue q;
    init(&q);
    push(&q, root);

    while (q.size != 0) {
        int count = q.size;
        result[resultSize] = (int *) malloc(count * sizeof(int));
        resultColSize[resultSize] = count;
        for (int i = 0; i < count; i++) {
            Type t = pop(&q);
            if (t == NULL) {
                continue;
            }
            result[resultSize][i] = t->val;

            if (t->left != NULL) {
                push(&q, t->left);
            }
            if (t->right != NULL) {
                push(&q, t->right);
            }
        }
        resultSize++;
    }

    destroy(&q);

    *returnSize = resultSize;
    *returnColumnSizes = resultColSize;
    return result;
}

int main(int argc, char const *argv[])
{
    return 0;
}